package _01_第一季.映射07;

import _01_第一季._00_公共接口.Map;
import _01_第一季.映射07.printer.BinaryTreeInfo;
import _01_第一季.映射07.printer.BinaryTrees;

import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;

public class HashMap<K,V> implements Map<K,V> {
    private static final boolean RED = false;
    private static final boolean BLACK = true;
    private int size; //红黑树上的所有节点总数
    private Node<K,V>[] table;
    private static final int DEFAULT_CAPACITY = 1 << 4;
    //负载因子 节点总数量/桶数组长度  如果超过0.75，就扩容为原来的2倍
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;

    public HashMap(){
        table = new Node[DEFAULT_CAPACITY];
    }

    private static class Node<K,V>{
        int hash;
        K key;
        V value;
        boolean color = RED;
        Node<K,V> left;
        Node<K,V> right;
        Node<K,V> parent;
        public Node(){
            this(null,null,null);
        }
        public Node(K key,V value,Node<K,V> parent){
            this.key = key;
            int hash = key == null ? 0 : key.hashCode();
            this.hash = hash ^ (hash >>> 16);
            this.value = value;
            this.parent = parent;
        }

        public boolean isLeaf(){
            return left == null && right == null;
        }
        public boolean hasTwoKids(){
            return left!=null && right != null;
        }
        public boolean isLeftChild(){
            return parent!=null && this == parent.left;
        }
        public boolean isRightChild(){
            return parent!=null && this == parent.right;
        }
        //返回兄弟节点
        public Node<K,V> sibling(){
            if(isLeftChild()){
                return parent.right;
            }
            if(isRightChild()){
                return parent.left;
            }
            return null;
        }

        @Override
        public String toString() {
            return "Node_"+key+"_"+value;
        }

    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size==0;
    }

    @Override
    public void clear() {
        if(size == 0) return;
        size = 0;
        for (int i = 0; i < table.length; i++) {
            table[i] = null;
        }
    }

    //添加的方法
    @Override
    public V put(K key, V value) {
        resize(); //判断是否需要扩容

        int index = index(key);
        Node<K,V> root = table[index];
        if(root == null){
            root = new Node<>(key,value,null);
            table[index] = root;
            size++;
            afterPut(root);
            return null;
        }

        Node<K,V> node = root;
        Node<K,V> parent = root;
        Node<K,V> result = null;
        boolean searched = false;
        int cmp = 0;
        K k1 = key;
        int h1 = hash(k1);
        do{
            parent = node;
            K k2 = node.key;
            int h2 = node.hash;

            if(h1>h2){
                cmp = 1;
            }else if(h1<h2){
                cmp = -1;
            }else if(Objects.equals(k1,k2)){
                cmp = 0;
            }else if(k1 != null && k2 !=null
                     && k1.getClass() == k2.getClass()
                     && k1 instanceof Comparable
                     && (cmp = ((Comparable)k1).compareTo(k2))!=0){
                //需要排除不equals,但是compare结果为0的情况，这种情况不能判断两个对象相等
                //如果两个也不compare,cmp已经赋值了，什么都不做，下面进行判断即可
            }else if(searched){
                cmp = System.identityHashCode(k1) - System.identityHashCode(k2);
            }else{
                if((node.left!=null && (result = node(node.left,k1))!=null)
                    || (node.right!=null && (result=node(node.right,k1))!=null)){
                    node = result;
                    cmp = 0;
                }else{
                    searched = true;
                    cmp = System.identityHashCode(k1) - System.identityHashCode(k2);
                }
            }

            if(cmp>0){
                node = node.right;
            }else if(cmp<0){
                node = node.left;
            }else{
                V ret = node.value;
                node.key = key;
                node.value = value;
                node.hash = h1;
                return ret;
            }
        }while (node!=null);

        Node<K,V> newNode = new Node<>(key,value,parent);
        if(cmp>0){
            parent.right = newNode;
        }else{
            parent.left = newNode;
        }
        size++;
        afterPut(newNode);
        return null;
    }

    //扩容
    private void resize() {
        if(size/table.length<=DEFAULT_LOAD_FACTOR) return;

        Node<K,V>[] oldTable = table;
        table = new Node[oldTable.length << 1];
        Queue<Node<K,V>> queue = new LinkedList<>();
        for(int i=0;i<oldTable.length;++i){
            if(oldTable[i] == null) continue;

            queue.offer(oldTable[i]);

            while(!queue.isEmpty()){
                Node<K,V> node = queue.poll();

                if(node.left!=null){
                    queue.offer(node.left);
                }

                if(node.right!=null){
                    queue.offer(node.right);
                }

                moveNode(node);
            }
        }
    }

    //移动节点的方法
    private void moveNode(Node<K, V> newNode) {
        newNode.left = null;
        newNode.right = null;
        newNode.parent = null;
        newNode.color = RED;

        int index = index(newNode);
        Node<K,V> root = table[index];
        if(root == null){
            root = newNode;
            table[index] = root;
            afterPut(root);
            return;
        }

        // 添加新的节点到红黑树上面
        Node<K, V> parent = root;
        Node<K, V> node = root;
        int cmp = 0;
        K k1 = newNode.key;
        int h1 = newNode.hash;
        do{
            parent = node;
            K k2 = node.key;
            int h2 = node.hash;
            if(h1>h2){
                cmp = 1;
            }else if(h1<h2){
                cmp = -1;
            }else if (k1 != null && k2 != null
                    && k1 instanceof Comparable
                    && k1.getClass() == k2.getClass()
                    && (cmp = ((Comparable)k1).compareTo(k2)) != 0) {
            } else {
                cmp = System.identityHashCode(k1) - System.identityHashCode(k2);
            }

            if (cmp > 0) {
                node = node.right;
            } else if (cmp < 0) {
                node = node.left;
            }

        }while (node!=null);

        // 看看插入到父节点的哪个位置
        newNode.parent = parent;
        if (cmp > 0) {
            parent.right = newNode;
        } else {
            parent.left = newNode;
        }

        // 新添加节点之后的处理
        afterPut(newNode);
    }

    @Override
    public V get(K key) {
        Node<K, V> node = node(key);
        return node == null ? null : node.value;
    }

    /**
     * 根据key找到对应的节点并返回
     * @param key 外部传进来的key
     * @return
     */
    private Node<K,V> node(K key){
        //先找到对应节点根据key,根节点
        Node<K,V> root = table[index(key)];
        return  root == null ? null : node(root,key);
    }

    /**
     * 去根节点为node的红黑树找key
     * @param node
     * @param k1
     * @return
     */
    private Node<K,V> node(Node<K,V> node,K k1){
        int h1 = hash(k1);
        Node<K,V> resultNode = null;
        int cmp = 0;
        while(node!=null){
            K k2 = node.key;
            int h2 = node.hash;
            if(h1>h2){
                node = node.right;
            }else if(h1<h2){
                node = node.left;
            }else if(Objects.equals(k1,k2)){
                return node;
            }else if(k1!=null && k2 !=null
                    && k1.getClass() == k2.getClass()
                    && k1 instanceof Comparable
                    && (cmp = ((Comparable)k1).compareTo(k2))!=0){
                //也需要排除equals不相等，但是compare相等的情况
                node = cmp > 0 ? node.right : node.left;
            //4.哈希值相等，不equals,也不具备可比较性,递归去根节点的右子树查找
            }else if(node.right!=null && (resultNode = node(node.right,k1)) !=null){
                return resultNode;
            }else{
                //5.去左子树查找,减少递归调用次数，提升性能
                node = node.left;
            }
        }
        return null;
    }

    @Override
    public V remove(K key) {
        return remove(node(key));
    }

    /**
     * 删除某一个节点
     * @param node
     * @return
     */
    private V remove(Node<K,V> node){
        if(node == null) return null;
        V oldValue = node.value;
        size--;

        //首先考虑删除度为2的节点，找到其前驱节点或者后继节点，将其转换为删除度为1或者度为0的节点
        if(node.hasTwoKids()){
            Node<K,V> pre = predecessor(node);
            node.key = pre.key;
            node.value = pre.value;
            node.hash = pre.hash;
            node = pre; //下面统一进行处理
        }

        //删除度为1或者度为0的节点
        Node<K,V> replacement = node.left != null ? node.left : node.right;
        int index = index(node); //传入一个节点，返回对应的索引，就可以找到他的根节点，因为哈希冲突才会在一颗红黑树上
        if(replacement != null){ //删除度为1的节点
            replacement.parent = node.parent;
            if(node.parent == null){ //删除度为1的根节点
                table[index] = replacement;
            } else if(node.isLeftChild()){
                node.parent.left = replacement;
            }else{
                node.parent.right = replacement;
            }
            //删除度为1的节点以后的调整
            afterRemove(replacement);
        }else if(node.parent == null){ //删除度为0的根节点
            table[index] = null;
            //删除度为0的根节点以后的调整
            afterRemove(node);
        }else{ //删除度为0的叶子节点
            if(node.isLeftChild()){
                node.parent.left = null;
            }else{
                node.parent.right = null;
            }
            //删除度为0的叶子节点以后的调整
            afterRemove(node);
        }
        return oldValue;
    }

    @Override
    public boolean containsKey(K key) {
        return node(key)!=null;
    }

    @Override
    public boolean containsValue(V value) {
        if(size == 0) return false;
        Queue<Node<K,V>> queue = new LinkedList<>();
        for(int i=0;i<table.length;++i){
            if(table[i] == null) continue;

            queue.offer(table[i]);
            while(!queue.isEmpty()){
                Node<K,V> node = queue.poll();
                if(Objects.equals(node.value,value)) return true;

                if(node.left!=null){
                    queue.offer(node.left);
                }

                if(node.right!=null){
                    queue.offer(node.right);
                }
            }
        }
        return false;
    }

    private int hash(K key){
        if(key == null) return 0; //支持key为null,如果为null,默认都放在0索引处
        int hash = key.hashCode();//拿到key对应的哈希值
        //防止你自己重写的hashCode方法取值不均匀
        //在将你的哈希值的高16位和低16位在进行异或混合计算
        return hash ^ (hash >>> 16);
    }

    private int index(K key){
        return hash(key) & table.length-1;
    }

    private int index(Node<K,V> node){
        return node.hash & table.length-1;
    }

    @Override
    public void traversal(Visitor<K, V> visitor) {
        if(size == 0 || visitor == null) return;
        Queue<Node<K,V>> queue = new LinkedList<>();
        for(int i=0;i<table.length;++i){
            if(table[i] == null) continue;//当前索引没有元素，直接跳过

            queue.offer(table[i]); //根节点入队
            while (!queue.isEmpty()){
                Node<K, V> node = queue.poll();
                //如果返回true，终止遍历
                if(visitor.visit(node.key,node.value)) return;

                if(node.left!=null){
                    queue.offer(node.left);
                }
                if(node.right!=null){
                    queue.offer(node.right);
                }
            }
        }
    }

    //找到该节点的后继节点:中序遍历时的后一个节点
    private Node<K,V> successor(Node<K,V> node){
        Node<K,V> suc = node.right;

        //情况1
        if(suc!=null){
            while(suc.left!=null){
                suc = suc.left;
            }
            return suc;
        }

        //情况2 终止条件 前驱节点在父节点的左子树中
        while(node.parent!=null && node == node.parent.right){
            node = node.parent;
        }
        return node.parent;
    }

    //找到该节点的前驱节点:中序遍历时的前一个节点
    private Node<K,V> predecessor(Node<K,V> node){
        if(node == null) return null;
        Node<K,V> pre = node.left;
        //情况1
        if(pre!=null){
            while(pre.right!=null){
                pre = pre.right;
            }
            return pre;
        }

        //情况2 终止条件 前驱节点在父节点的右子树中
        while(node.parent!=null && node == node.parent.left){
            node = node.parent;
        }
        return node.parent;
    }

    /**
     * 添加之后的修复
     * @param node
     */
    private void afterPut(Node<K, V> node) {
        Node<K,V> parent = node.parent;
        //添加的是根节点或者上溢到达了根节点，直接染成黑色返回即可
        if(parent == null){
            black(node);
            return;
        }

        //情况1 父节点是黑色
        if(isBlack(parent)) return;

        //拿到叔父节点，根据判定条件
        Node<K,V> uncle = parent.sibling();
        //祖父节点
        Node<K,V> grand = parent.parent;

        //情况3 叔父节点是红色 上溢
        if(isRed(uncle)){
            black(parent);
            black(uncle);
            afterPut(red(grand)); //递归处理
            return;
        }

        //情况2 叔父节点不是红色 旋转
        if(parent.isLeftChild()){
            red(grand);
            if(node.isLeftChild()){ //LL
                black(parent);
            }else{ //LR
                black(node);
                rotateLeft(parent);
            }
            rotateRight(grand);
        }else{
            red(grand);
            if(node.isLeftChild()){ //RL
                black(node);
                rotateRight(parent);
            }else{ //RR
                black(parent);
            }
            rotateLeft(grand);
        }
    }

    /**
     * 删除之后的修复
     * @param node
     */
    private void afterRemove(Node<K, V> node) {
        if(isRed(node)){
            black(node);
            return;
        }

        //删除的是根节点
        Node<K,V> parent = node.parent;
        if(parent == null) return;

        //删除黑色叶子节点
        //需要找到兄弟节点，但是兄弟节点在之前的删除逻辑中父节点的那根线已经断了，无法通过node.sibling()找到兄弟节点
        //逆向思维 判断被删除的节点在左还是右
        boolean left = parent.left == null || node.isLeftChild(); //下溢后产生的下溢现象，可以用第二个条件判断
        Node<K,V> sibling = left ? parent.right : parent.left;

        if(left){ //被删除的节点在左边 兄弟节点在右边
            //删除的节点在左边和删除的节点在右边逻辑完全一样，只是方向相反
            if(isRed(sibling)){
                black(sibling);
                red(parent);
                rotateLeft(parent);
                sibling = parent.right;
            }
            if(isBlack(sibling.left) && isBlack(sibling.right)){
                //没有，借不了
                boolean parentBlack = isBlack(parent);
                black(parent);
                red(sibling);
                if(parentBlack){ //父节点是黑色的情况，导致父节点也会下溢
                    afterRemove(parent);
                }
            }else{
                //有至少一个，可以借
                if(isBlack(sibling.right)){
                    rotateRight(sibling);
                    sibling = parent.right; //旋转以后 兄弟节点也变了
                }
                color(sibling,colorOf(parent));
                black(sibling.right);
                black(parent);
                rotateLeft(parent);
            }

        }else{ //被删除的在右边 兄弟节点在左边

            //先考虑兄弟节点是红色的情况，将其转成兄弟节点为黑色的情况,下面就能统一处理
            if(isRed(sibling)){
                black(sibling);
                red(parent);
                rotateRight(parent);
                sibling = parent.left;
            }

            //其次考虑兄弟节点是黑色的情况
            //看兄弟节点是否有一个红色的子节点可以借
            if(isBlack(sibling.left) && isBlack(sibling.right)){
                //没有，借不了
                boolean parentBlack = isBlack(parent);
                black(parent);
                red(sibling);
                if(parentBlack){ //父节点是黑色的情况，导致父节点也会下溢
                    afterRemove(parent);
                }
            }else{
                //有至少一个，可以借
                //先处理需要双旋的情况，兄弟节点的左节点是黑色，将兄弟节点左旋转，后面即可统一处理
                if(isBlack(sibling.left)){
                    rotateLeft(sibling);
                    sibling = parent.left; //旋转以后 兄弟节点也变了
                }
                //统一对父节点进行右旋转,再将中心节点染成和父节点一样的颜色，左右节点染成黑色
                //中心节点其实也就是兄弟节点
                color(sibling,colorOf(parent));
                black(sibling.left);
                black(parent);
                rotateRight(parent);
            }
        }
    }

    //旋转之后更新父节点以及高度的统一操作
    private void afterRotate(Node<K,V> grand, Node<K,V> parent, Node<K,V> child){
        //更新p的父节点
        parent.parent = grand.parent;
        if(grand.isLeftChild()){
            grand.parent.left = parent;
        }else if(grand.isRightChild()){
            grand.parent.right = parent;
        }else{
            table[index(grand)] = parent;
        }

        //更新child的父节点
        if(child!=null){
            child.parent = grand;
        }

        //更新grand的父节点
        grand.parent = parent;

    }

    //左旋转
    private void rotateLeft(Node<K,V> grand){
        Node<K,V> parent = grand.right;
        Node<K,V> child = parent.left;

        //换线
        grand.right = child;
        parent.left = grand;

        //旋转之后更新父节点以及高度的操作
        afterRotate(grand,parent,child);

    }

    //右旋转
    private void rotateRight(Node<K,V> grand){
        Node<K,V> parent = grand.left;
        Node<K,V> child = parent.right;
        grand.left = child;
        parent.right = grand;

        //旋转之后更新父节点以及高度的操作
        afterRotate(grand,parent,child);

    }

    /**
     * 对节点染色的方法
     * @param node 待染色的节点
     * @param color 颜色
     * @return 返回染色后的节点
     */
    private Node<K,V> color(Node<K,V> node, boolean color){
        if(node == null) return null;
        node.color = color;
        return node;
    }

    /**
     * 将节点染成红色
     * @param node 带染色的节点
     * @return 返回染成红色的节点
     */
    private Node<K,V> red(Node<K,V> node){
        return color(node,RED);
    }

    /**
     * 将节点染成黑色
     * @param node 带染色的节点
     * @return 返回染成黑色的节点
     */
    private Node<K,V> black(Node<K,V> node){
        return color(node,BLACK);
    }

    /**
     * 判断节点颜色的方法
     * @param node
     * @return 返回节点的颜色
     */
    private boolean colorOf(Node<K,V> node){
        return node == null ? BLACK : node.color;
    }

    //判断节点颜色是否是红色
    private boolean isRed(Node<K,V> node){
        return colorOf(node) == RED;
    }

    //判断节点颜色是否是黑色
    private boolean isBlack(Node<K,V> node){
        return colorOf(node) == BLACK;
    }

    //打印哈希表，以红黑树的方式
    public void print(){
        if(size == 0) return;
        for (int i = 0; i < table.length; i++) {
            System.out.println("【index = " + i + "】");
            final Node<K,V> root = table[i];
            BinaryTrees.println(new BinaryTreeInfo() {
                @Override
                public Object root() {
                    return root;
                }

                @Override
                public Object left(Object node) {
                    return ((Node<K,V>)node).left;
                }

                @Override
                public Object right(Object node) {
                    return ((Node<K,V>)node).right;
                }

                @Override
                public Object string(Object node) {
                    return node;
                }
            });
            System.out.println("-----------------------------------");
        }
    }
}
